package aws;

import java.util.*;

/**
 * 字符串组合
 */
public class WordCompose {

    private Map<String, String> compose(String []str) {
        List<String> wordsList = Arrays.asList(str);
        Collections.sort(wordsList);

        Map<String, String> map = new HashMap<>();

        for(int i=0; i<wordsList.size()-1; i++) {
            String word = wordsList.get(i);
            int j = i+1;
            while (wordsList.get(j).startsWith(word)) {
                String remain = wordsList.get(j).replace(word,"");
                if(wordsList.contains(remain)) {
                    map.put(wordsList.get(j), word+","+remain);
                }
                j++;
            }
        }

        return map;
    }

    private List<String> composeResult(String []str) {

        List<String> result = new ArrayList<>();
        Map<String, String> map = this.compose(str);

        Queue<String> queue = new ArrayDeque<>();
        for(Map.Entry<String, String> entry : map.entrySet()) {
            List<String> oneWordList = new ArrayList<>();
            String value = entry.getValue();
            String []valueArray = value.split(",");
            queue.addAll(Arrays.asList(valueArray));

            while (!queue.isEmpty()) {
                String element = queue.poll();
                if(map.get(element) != null) {
                    queue.addAll(Arrays.asList(map.get(element).split(",")));
                } else {
                    oneWordList.add(element);
                }
            }
            result.add(String.join(",", oneWordList));
        }

        result.stream().forEach(item->{
            System.out.println(item);
        });

        return result;

    }

    public static void main(String[] args) {
        String [] str = new String[]{"rockstar","rock","star","rocks","tar","stars","rockstars","super","highway",
        "high","way","superhighway"};

        new WordCompose().composeResult(str);
    }
}
